#coding=utf-8
'''
Created on 2012-10-28

@author: infear
'''
#http://blog.csdn.net/yysdsyl/article/details/4210871
#歌德巴赫猜想说任何一个不小于6的偶数都可以分解为两个奇素数之和。对此问题扩展，如果一个整数能够表示成两个或多个素数之和，则得到一个素数和分解式。
#对于一个给定的整数，输出所有这种素数和分解式。注意，对于同构的分解只输出一次（比如5只有一个分解2 + 3，而3 + 2是2 + 3的同构分解式）。
#例如，对于整数8，可以作为如下三种分解：
#(1) 8 = 2 + 2 + 2 + 2
#(2) 8 = 2 + 3 + 3
#(3) 8 = 3 + 5

def isNotPrime(n):
    if n==2 or n==3:
        return False
    for i in range(2,n/2+1):
        if n%i==0:
            return True
    return False
    
def getPrimeSet(N):
    primeList=[]
    for i in range(2,N):
        if not isNotPrime(i):
            primeList.append(i)
    return primeList

def getComposite(N,prime_list):
    #print "getComposite",N,prime_list
    if prime_list is None or len(prime_list)==0:
        pass
    elif N==0:
        yield ()
    else:
        max=prime_list[len(prime_list)-1]
        if not (N-1==max or max>N):
            for result in getComposite(N-max,prime_list):
                yield result+(max,)
        for result in getComposite(N,prime_list[0:len(prime_list)-1]):
                yield result

primeSet=getPrimeSet(8)
print primeSet
print list(getComposite(8,primeSet))